import javax.print.DocFlavor;
import java.util.*;

public class project {
    public int countVowelStrings(int n) {
        return (n+4)*(n+3)*(n+2)*(n+1)/24;
    }











    public List<List<Integer>> threeSum(int[] nums) {
        if(nums==null||nums.length<3){
            return new ArrayList<>();
        }
        Set<List<Integer>> set=new HashSet<>();
        Arrays.sort(nums);
        for(int i=0;i<nums.length;i++){
            int left=i+1;
            int right=nums.length-1;
            int tmp=-nums[i];
            while(left<right){
                int sum=nums[left]+nums[right];
                if(sum==tmp){
                    set.add(Arrays.asList(nums[i],nums[left],nums[right]));
                    left++;
                    right--;
                }else if(sum<tmp){
                    left++;
                }else{
                    right--;
                }
            }
        }
        return new ArrayList<>(set);
    }










    public List<List<Integer>> threeSum1(int[] nums) {
        if(nums==null||nums.length<3){
            return new ArrayList<>();
        }
        Set<List<Integer>> set=new HashSet<>();
        Arrays.sort(nums);
        for(int i=0;i<nums.length;i++){
            int tmp=-nums[i];
            int left=i+1;
            int right=nums.length-1;
            while(left<right){
                int sum=nums[left]+nums[right];
                if(sum==tmp){
                    set.add(Arrays.asList(nums[i],nums[left],nums[right]));
                    left++;
                    right--;
                }else if(sum<tmp){
                    left++;
                }else{
                    right--;
                }
            }
        }
        return new ArrayList<>(set);
    }












    public int lengthOfLongestSubstring(String s) {
        Map<Character,Integer> map=new HashMap<>();
        int i=0;
        int max=0;
        for(int j=0;j<s.length();j++){
            if(map.containsKey(s.charAt(j))){
                i=Math.max(map.get(s.charAt(j))+1,i);
            }
            map.put(s.charAt(j),j);
            max=Math.max(j-i+1,max);
        }
        return max;
    }











    int ret=Integer.MAX_VALUE;
    public int coinChange(int[] coins, int amount) {
        if(amount<1){
            return 0;
        }
        int count=0;
        dfs(coins,amount,count);
        return ret==Integer.MAX_VALUE?-1:ret;
    }
    public void dfs(int[] arr,int key,int count){
        if(key<0){
            return;
        }
        if(key==0){
            ret=Math.min(ret,count);
            return;
        }
        for(int i=0;i<arr.length;i++){
            dfs(arr,key-arr[i],count+1);
        }
    }













    public int integerBreak(int n) {
        if(n<=3){
            return n-1;
        }
        int a=n/3;
        int b=n%3;
        if(b==0){
            return (int)Math.pow(3,a);
        }else if(b==1){
            return (int)Math.pow(3,a-1)*4;
        }
        return (int) Math.pow(3,a)*2;
    }












    public int cuttingRope1(int n) {
        if(n<=3){
            return n-1;
        }
        int a=n/3;
        int b=n%3;
        if(b==0){
            return (int)Math.pow(3,a);
        }else if(b==1){
            return (int) Math.pow(3,a-1)*4;
        }else{
            return (int) Math.pow(3,a)*2;
        }
    }











    boolean[] booleans;
    Set<String> set=new HashSet<>();
    public String[] permutation(String s) {
        booleans=new boolean[s.length()];
        StringBuilder sb=new StringBuilder();
        dfs3(s,sb);
        return (String[]) set.toArray(new String[set.size()]);
    }
    public void dfs3(String s,StringBuilder sb){
        if(sb.length()==s.length()){
            set.add(sb.toString());
        }
        for(int i=0;i<s.length();i++){
            if(booleans[i]){
                continue;
            }
            booleans[i]=true;
            sb.append(s.charAt(i));
            dfs3(s,sb);
            booleans[i]=false;
            sb.deleteCharAt(sb.length()-1);
        }
    }










    int count=0;
    public int findTargetSumWays(int[] nums, int target) {
        dfs2(nums,target,0,0);
        return count;
    }
    public void dfs2(int[] arr,int target,int len,int sum){
        if(len==arr.length){
            if(target==sum){
                count++;
            }
        }else{
            dfs2(arr,target,len+1,sum+arr[len]);
            dfs2(arr,target,len+1,sum-arr[len]);
        }
    }











    int count1=0;
    public int findTargetSumWays1(int[] nums, int target) {
        dfs1(nums,target,0,0);
        return count1;
    }
    public void dfs1(int[] arr,int target,int len,int sum){
        if(len==arr.length){
            if(sum==target){
                count1++;
            }
        }
        dfs1(arr,target,len+1,sum-arr[len]);
        dfs1(arr,target,len+1,sum+arr[len]);
    }













    public int[] constructArr(int[] a) {
        int len=a.length;
        int[] dp=new int[len];
        dp[0]=1;
        for(int i=1;i<len;i++){
            dp[i]=dp[i-1]*a[i-1];
        }
        int tmp=1;
        for(int i=len-2;i>=0;i--){
            tmp*=a[i+1];
            dp[i]*=tmp;
        }
        return dp;
    }
}
